/*
*    Qizx/open 3.0 beta
*
* This code is the open-source version of Qizx.
* Copyright (C) 2004-2009 Axyana Software -- All rights reserved.
*
* The contents of this file are subject to the Mozilla Public License 
*  Version 1.1 (the "License"); you may not use this file except in 
*  compliance with the License. You may obtain a copy of the License at
*  http://www.mozilla.org/MPL/
*
* Software distributed under the License is distributed on an "AS IS" basis,
*  WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
*  for the specific language governing rights and limitations under the
*  License.
*
* The Initial Developer of the Original Code is Xavier Franc - Axyana Software.
*
*/
using System;
namespace System.Qizx.Util.Basic
{
	
	/// <summary> A simple hash table meant for efficiency. The key (subclass of Key) also
	/// bears the value.
	/// </summary>
	public class HTable
	{
		virtual public int Size
		{
			get
			{
				return count;
			}
			
		}
		/// <summary> Special purpose.</summary>
		virtual public Key[] Hash
		{
			get
			{
				return _hash;
			}
			
		}
		internal const double LOAD_FACTOR = 1.0;
		
		protected internal Key[] _hash;
		protected internal int count = 0;
		protected internal int maxCount;
		
		
		public HTable(int capacity)
		{
			_hash = new Key[capacity];
			maxCount = (int) (LOAD_FACTOR * _hash.Length);
		}
		
		public HTable():this(3)
		{
		}
		
		/// <summary> Must of course implement hashCode() and equals().</summary>
		public abstract class Key
		{
			public Key next;
			
			public abstract Key duplicate();
		}
		
		public virtual Key Get(Key probe)
		{
			int h = hash(probe);
			for (Key c = _hash[h]; c != null; c = c.next)
				if (c.Equals(probe))
					return c;
			return null;
		}
		
		public virtual int hash(Key key)
		{
			return hashFunction(key.GetHashCode()) % _hash.Length;
		}
		
		public static int hashFunction(int hashcode)
		{
			return (hashcode & 0x7FFFFFFF);
		}
		
		public virtual Key put(Key probe)
		{
			int h = hash(probe);
			for (Key c = _hash[h]; c != null; c = c.next)
				if (c.Equals(probe))
					return c;
			if (++count > maxCount)
			{
				resize();
				h = hash(probe); // may have changed
			}
			Key nc = probe.duplicate();
			nc.next = _hash[h];
			_hash[h] = nc;
			return nc;
		}
		
		/// <summary> Like put, but returns true if the key was not found.</summary>
		public virtual bool hasPut(Key probe)
		{
			int h = hash(probe);
			for (Key c = _hash[h]; c != null; c = c.next)
				if (c.Equals(probe))
					return false;
			if (++count > maxCount)
			{
				resize();
				h = hash(probe); // may have changed
			}
			Key nc = probe.duplicate();
			nc.next = _hash[h];
			_hash[h] = nc;
			return true;
		}
		
		/// <summary> No check: allows duplicate keys.</summary>
		public virtual Key add(Key probe)
		{
			int h = hash(probe);
			Key nc = probe.duplicate();
			nc.next = _hash[h];
			_hash[h] = nc;
			++count;
			return nc;
		}
		
		public virtual void  directPut(Key entry)
		{
			if (++count > maxCount)
				resize();
			int h = hash(entry);
			entry.next = _hash[h];
			_hash[h] = entry;
		}
		
		public virtual Key[] getKeys(Key[] keys)
		{
			int s = 0;
			for (int h = _hash.Length; --h >= 0; )
				for (Key c = _hash[h]; c != null; c = c.next)
					keys[s++] = c;
			return keys;
		}
		
		public virtual void  clear()
		{
			for (int h = _hash.Length; --h >= 0; )
				_hash[h] = null;
			count = 0;
		}
		
		internal virtual void  resize()
		{
			Key[] old = _hash;
			
			int emptyC = 0;
			for (int i = 0; i < _hash.Length; i++)
				if (_hash[i] == null)
					emptyC++;
			_hash = new Key[old.Length * 2 + 1];
			for (int ic = old.Length; --ic >= 0; )
			{
				for (Key c = old[ic]; c != null; )
				{
					Key ac = c;
					c = c.next;
					int h = hash(ac);
					ac.next = _hash[h];
					_hash[h] = ac;
				}
			}
			maxCount = (int) (LOAD_FACTOR * _hash.Length);
		}
	}
}